import java.util.Stack;

/**
 * @author VernHe
 * @date 2021年05月19日 14:57
 */
public class Solution_085 {
    public static void main(String[] args) {
        char[][] maxtrix = new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        System.out.println(new Solution_085().maximalRectangle(maxtrix));
    }

    public int maximalRectangle(char[][] matrix) {
        // 参数判断
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        // 变量定义及初始化
        int res = 0;
        int curValue;
        int[][] arrs = new int[matrix.length][matrix[0].length];
        // 循环
//        for (int i = matrix.length - 1; i >= 0; i--) {
//            int[] arr = new int[matrix[0].length];
        for (int col = 0; col < matrix[0].length; col++) {
            int sum = 0;
            int row = matrix.length - 1;
            while (row >= 0) {
                if (matrix[row][col] == '1') {
                    sum++;
                } else {
                    sum = 0;
                }
                System.out.println("sum: " + sum);
                arrs[row][col] = sum;
                row--;
            }

//                int row = i;
//                int sum = 0;
//                while (row >= 0 && matrix[row][col] == '1') {
//                    sum++;
//                    row--;
//                }
//                arr[col] = sum;
//                System.out.println("循环创建数组");
//                System.out.println(sum);
        }
//            for (int i1 : arr) {
//                System.out.printf(i1 + " ");
//            }
//            System.out.println();
//            res = Math.max(res,largestRectangleArea(arr));
//            System.out.println("最新的res");
//            System.out.println(res);
//            System.out.println("--------------------");
//        }

        for (int[] arr : arrs) {
            for (int i : arr) {
                System.out.printf(i + " ");
            }
            System.out.println();
        }
        for (int i = 0; i < arrs.length; i++) {
            res = Math.max(res, largestRectangleArea(arrs[i]));
        }

        // 返回结果
        return res;
    }

    private int largestRectangleArea(int[] heights) {
        int res = 0;
        // 参数判断
        if (heights == null || heights.length == 0) {
            return res;
        }
        // 在原有基础上两边补0
        int[] new_heights = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            new_heights[i + 1] = heights[i];
        }
        // 定义变量
        // 单调递增栈，用于保存高度
        Stack<Integer> stack = new Stack();
        // 初始化
        // 先入栈一个
        stack.add(0);
        for (int i = 1; i < new_heights.length; i++) {
            while (!stack.isEmpty() && new_heights[stack.peek()] >= new_heights[i]) {
                int curIndex = stack.pop();
                if (stack.isEmpty()) {
                    res = Math.max(res, new_heights[curIndex] * (i - curIndex));
                } else {
                    int preIndex = stack.peek();
                    res = Math.max(res, new_heights[curIndex] * (i - preIndex - 1));
                }
            }
            stack.add(i);
        }
        return res;
    }
}
